package LeetCode.month02.day35;

import java.util.*;

public class Main {
    // 数位和数组，预处理减少重复运算
    static int[] digitSum;

    // 预计算数位和函数
    static void calcDigitSum(int maxVal) {
        digitSum = new int[maxVal];
        for (int i = 0; i < maxVal; i++) {
            int num = i, tmp = 0;
            while (num > 0) {
                tmp += num % 10;
                num /= 10;
            }
            digitSum[i] = tmp;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt(), n = scanner.nextInt(), k = scanner.nextInt();
        scanner.close();

        if (m == 0 || n == 0) {
            System.out.println(0);
            return;
        }

        calcDigitSum(Math.max(m, n));

        // 四个方向
        int[][] direct = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        queue.add(0);
        visited.add(0);
        int res = 1;

        while (!queue.isEmpty()) {
            int num = queue.poll();
            int x = num / n, y = num % n;

            for (int[] d : direct) {
                int newX = x + d[0], newY = y + d[1];
                int newNum = newX * n + newY;

                // 越界 和 已经访问过
                if (newX < 0 || newX >= m || newY < 0 || newY >= n || visited.contains(newNum)) {
                    continue;
                }
                // 数位和超过 k
                if (digitSum[newX] + digitSum[newY] > k) {
                    continue;
                }
                res++;
                queue.add(newNum);
                visited.add(newNum);
            }
        }

        System.out.println(res);
    }
}
